package com.jxm.linear;

/**
 * @Author: jxm
 * @Description: 快慢指针解决单项链表有环节点入口问题
 * @Date: 2022/6/13 23:59
 * @Version: 1.0
 */
public class CircleListIn {

    /**
     * break :可以用来从循环体内中途跳出循环体，即提前结束循环操作，接着执行循环下面的语句
     * continue: 其作用为结束本次循环，即跳过循环体中下面尚未执行的语句，接着进行下一次是否执行循环的判定。
     * @param args
     */

    public static void main(String[] args) {
        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fourth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> six = new Node<String>("ff", null);
        Node<String> seven = new Node<String>("gg", null);
        //完成结点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;
        //产生环
        seven.next = fourth;

        //判断链表是否有环
        Node entrance = getEntrance(first);
        System.out.println("first链表环入口元素为："+entrance.item);
    }

    /**
     * 查找有环入口问题
     * @param first  链表首结点
     * @return 环的入口节点
     */
    public static Node getEntrance(Node<String> first) {
        //定义快慢两个指针
        Node<String> fast = first;
        Node<String> slow = first;
        //临时指针
        Node<String> temp = null;
        //遍历链表，先找到环（快慢指针相遇），准备一个临时指针，指向链表的首节点
        //继续遍历，直到慢指针和临时指针相遇，那么相遇是所指向的节点就是环的入口
        while (fast!=null && fast.next!=null){
            //变换快慢指针
            fast = fast.next.next;
            slow = slow.next;

            //判断快慢指针是否相遇
            if (fast.equals(slow)){
                temp = first;
                continue; //跳出本轮循环，不在执行循环体下面的语句
            }

            //让临时指针变换
            if(temp != null){
                temp = temp.next;
                //判断临时和慢指针是否相遇
                if(temp.equals(slow)){
                    break; //结束循环，执行循环下面的语句
                }
            }
        }

        return temp;
    }

    //结点类
    private static class Node<T> {
        //存储数据
        T item;
        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item; this.next = next;
        }
    }
}
